#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ElemType char
typedef struct BiTNode
{
    ElemType data;                   // 数据域
    struct BiTNode *lchild, *rchild; // 指针域(左右孩子)
} BiTNode, *BiTree;
typedef struct LinkNode
{
    BiTNode *data;
    struct LinkNode *next;
} LinkNode;
typedef struct
{
    LinkNode *front, *rear;
} LinkQueue;

void InitQueue(LinkQueue *);               // 初始化队列
bool QueueEmpty(LinkQueue *);              // 队列是否为空
void EnterQueue(LinkQueue *, BiTNode *);   // 入队
void DeleteQueue(LinkQueue *, BiTNode **); // 出队
void PreCreateBiTree(BiTree *);            // 先序遍历创建二叉链表树
void visit(BiTNode *);                     // 访问根节点并输出内容
void PreOrder(BiTree);                     // 先序遍历
void InOrder(BiTree);                      // 中序遍历
void PostOrder(BiTree);                    // 后序遍历
void LevelOrder(BiTree);                   // 层次遍历(要用到队列)
void PreOrderLeaves(BiTree);               // 先序只输出叶子结点
int InOrderCountLeaves(BiTree);            // 中序统计叶子节点数目
int PostTreeDepth(BiTree);                 // 后序遍历求二叉树高度
int depth = 0;                             // 全局变量
void PreTreeDepth(BiTree, int);            // 先序遍历求二叉树高度

int main()
{
    BiTree root;
    PreCreateBiTree(&root);

    LevelOrder(root);
    printf("\n");
    PreOrder(root);
    printf("\n");
    InOrder(root);
    printf("\n");
    PostOrder(root);
    printf("\n");

    PreOrderLeaves(root);
    printf("\n");

    printf("%d\n", InOrderCountLeaves(root));
    printf("%d\n", PostTreeDepth(root));
    PreTreeDepth(root, 1);
    printf("%d\n", depth);
    return 0;
}
void InitQueue(LinkQueue *pQ) // 初始化队列
{
    pQ->front = (LinkNode *)malloc(sizeof(LinkNode));
    if (pQ->front == NULL)
    {
        exit(-1);
    }
    pQ->rear = pQ->front;
    pQ->front->next = NULL;
    return;
}
bool QueueEmpty(LinkQueue *pQ) // 队列是否为空
{
    if (pQ->front == pQ->rear)
        return true;
    return false;
}
void EnterQueue(LinkQueue *pQ, BiTNode *val) // 入队
{
    pQ->rear->next = (LinkNode *)malloc(sizeof(LinkNode));
    if (pQ->rear->next == NULL)
    {
        exit(-1);
    }
    pQ->rear = pQ->rear->next;
    pQ->rear->data = val;
    pQ->rear->next = NULL;
    return;
}
void DeleteQueue(LinkQueue *pQ, BiTNode **pVal) // 出队
{
    if (QueueEmpty(pQ))
        return;
    LinkNode *temp = pQ->front->next;
    pQ->front->next = pQ->front->next->next;
    *pVal = temp->data;
    if (pQ->rear == temp)
    {
        pQ->rear = pQ->front;
    }
    free(temp);
    temp = NULL;
    return;
}
void PreCreateBiTree(BiTree *T) // 先序遍历创建二叉链表树
{
    ElemType ch;
    ch = getchar();
    getchar();
    if (ch == '.')
        *T = NULL;
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        PreCreateBiTree(&(*T)->lchild);
        PreCreateBiTree(&(*T)->rchild);
    }
}
void visit(BiTNode *T) // 访问根节点并输出内容
{
    printf("%c ", T->data);
    return;
}
void PreOrder(BiTree T) // 先序遍历
{
    if (T != NULL)
    {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
    return;
}
void InOrder(BiTree T) // 中序遍历
{
    if (T != NULL)
    {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
    return;
}
void PostOrder(BiTree T) // 后序遍历
{
    if (T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
    return;
}
void LevelOrder(BiTree T) // 层次遍历
{
    LinkQueue Q;
    InitQueue(&Q);
    EnterQueue(&Q, T);
    BiTNode *val;
    while (!QueueEmpty(&Q))
    {
        DeleteQueue(&Q, &val);
        visit(val);
        if (val->lchild != NULL)
            EnterQueue(&Q, val->lchild);
        if (val->rchild != NULL)
            EnterQueue(&Q, val->rchild);
    }
    return;
}
void PreOrderLeaves(BiTree T) // 先序只输出叶子结点
{
    if (T != NULL)
    {
        if (T->lchild == NULL && T->rchild == NULL)
            visit(T);
        PreOrderLeaves(T->lchild);
        PreOrderLeaves(T->rchild);
    }
    return;
}
int InOrderCountLeaves(BiTree T) // 中序统计叶子节点数目
{
    if (T == NULL)
        return 0;
    else if (T->lchild == NULL && T->rchild == NULL)
        return 1;
    else
        return InOrderCountLeaves(T->lchild) + InOrderCountLeaves(T->rchild);
}

int PostTreeDepth(BiTree T) // 后序遍历求二叉树高度
{
    int DepthLeft, DepthRight, max;
    if (T != NULL)
    {
        DepthLeft = PostTreeDepth(T->lchild);
        DepthRight = PostTreeDepth(T->rchild);
        max = DepthLeft > DepthRight ? DepthLeft : DepthRight;
        return max + 1;
    }
    return 0;
}
void PreTreeDepth(BiTree T, int h) // 先序遍历求二叉树高度
{
    if (T != NULL)
    {
        if (h > depth)
            depth = h;
        PreTreeDepth(T->lchild, h + 1);
        PreTreeDepth(T->rchild, h + 1);
    }
}